package com.tgy.leetcode;

class Solution {
    public int maxPathSum(TreeNode root) {

        if (root == null) {

            return 0;
        }

        int[] maxPath = new int[1];
        maxPath[0] = Integer.MIN_VALUE;
        postTraversal(root,maxPath);
        return maxPath[0];
    }

    private int postTraversal(TreeNode node, int[] maxPath) {

        if (node == null) {
            return 0;
        }

        int leftMaxPath = postTraversal(node.left, maxPath);
        int rightMaxPath = postTraversal(node.right, maxPath);

        leftMaxPath += node.val;
        rightMaxPath += node.val;
        maxPath[0] = Math.max(maxPath[0],Math.max(node.val,Math.max(leftMaxPath,rightMaxPath)));
        maxPath[0] = Math.max(maxPath[0],leftMaxPath + rightMaxPath - node.val);
        return Math.max(node.val,Math.max(leftMaxPath,rightMaxPath));
    }
}

public class _124_二叉树中的最大路径和_01 {

    public static void main(String[] args) {

        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(-10);
        t1.left = new TreeNode(9);
//        t1.left.left = new TreeNode(1);
//        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(20);
        t1.right.left = new TreeNode(-15);
        t1.right.right = new TreeNode(7);

        Solution solution = new Solution();

        System.out.println(solution.maxPathSum(t1));

    }
}
